#ifndef GRAPH_NORMALIZATION_H_
#define GRAPH_NORMALIZATION_H_

#include "Graph.h"
#include "RootedTree.h"

namespace masugo
{

template<typename VertexKeyType, typename VertexValueType, typename EdgeValueType>
class graph_normalization
{
public:
	typedef VertexKeyType VertexKey;
	typedef VertexValueType VertexValue;
	typedef EdgeValueType EdgeValue;
	typedef Graph<VertexKey, VertexValue, EdgeValue> FGraph;
	typedef FGraph FTree;
	typedef RootedTree<VertexKey, VertexValue, EdgeValue> RTree;

	static RTree construct_tree_canonical_form(const FTree& ftree)
	{
		const std::deque<VertexKey> root=select_tree_root(ftree);
		if(root.empty() || root.size()>2) { throw std::invalid_argument(utilities::ParametricString("Function {} called for a non-tree").arg(__FUNCTION__).str()); }
		if(root.size()==1)
		{
			return construct_rooted_ordered_tree(ftree, root.front());
		}
		else
		{
			FTree virtually_rooted_ftree=ftree;
			const VertexKey virtual_root_key=utilities::virtual_value<VertexKey>();
			const VertexValue virtual_root_value=utilities::virtual_value<VertexValue>();
			virtually_rooted_ftree.set_vertex_value(virtual_root_key, virtual_root_value);
			const EdgeValue virtual_edge_value=virtually_rooted_ftree.connection_value(root.front(), root.back());
			virtually_rooted_ftree.disconnect(root.front(), root.back());
			virtually_rooted_ftree.connect(root.front(), virtual_root_key, virtual_edge_value);
			virtually_rooted_ftree.connect(root.back(), virtual_root_key, virtual_edge_value);
			return construct_tree_canonical_form(virtually_rooted_ftree);
		}
	}

	static std::string construct_graph_maximal_spanning_tree_string(const FGraph& fgraph)
	{
		std::deque<RTree> maximal_trees;
		for(typename FGraph::Vertices::const_iterator it=fgraph.vertices().begin();it!=fgraph.vertices().end();it++)
		{
			RTree candidate(it->first, it->second.value);
			candidate.order();
			if(maximal_trees.empty() || candidate.canonical_string()==maximal_trees.back().canonical_string()) { maximal_trees.push_back(candidate); }
			else if(candidate.canonical_string()>maximal_trees.back().canonical_string()) { maximal_trees=std::deque<RTree>(1, candidate); }
		}
		while(!maximal_trees.empty() && maximal_trees.back().vertices().size()<fgraph.vertices().size())
		{
			std::deque<RTree> new_maximal_trees;
			for(std::size_t i=0;i<maximal_trees.size();i++)
			{
				const RTree& rtree=maximal_trees[i];
				for(typename RTree::Vertices::const_iterator it=rtree.vertices().begin();it!=rtree.vertices().end();it++)
				{
					const VertexKey& parent_key=it->first;
					const typename FGraph::Vertex& fgraph_vertex=fgraph.vertex(parent_key);
					for(typename FGraph::Vertex::Adjacency::const_iterator jt=fgraph_vertex.adjacency.begin();jt!=fgraph_vertex.adjacency.end();jt++)
					{
						const VertexKey& child_key=jt->first;
						if(!rtree.vertex_exists(child_key))
						{
							RTree candidate=rtree;
							candidate.add_child(parent_key, child_key, jt->second, fgraph.vertex(child_key).value);
							candidate.order();
							if(new_maximal_trees.empty() || candidate.canonical_string()==new_maximal_trees.back().canonical_string()) { new_maximal_trees.push_back(candidate); }
							else if(candidate.canonical_string()>new_maximal_trees.back().canonical_string()) { new_maximal_trees=std::deque<RTree>(1, candidate); }
						}
					}
				}
			}
			maximal_trees=new_maximal_trees;
		}
		if(maximal_trees.empty()) { throw std::invalid_argument(utilities::ParametricString("Function {} called for a not connected graph").arg(__FUNCTION__).str()); }
		return maximal_trees.back().canonical_string();
	}

private:
	static std::deque<VertexKey> select_tree_root(const FTree& ftree)
	{
		std::deque<VertexKey> result;
		FTree stripper=ftree;
		bool ended=false;
		while(!ended)
		{
			if(stripper.vertices().size()==1)
			{
				result.push_back(stripper.vertices().begin()->first);
				ended=true;
			}
			else if(stripper.vertices().size()==2)
			{
				typename FTree::Vertices::const_iterator it=stripper.vertices().begin();
				const VertexKey key1=it->first;
				it++;
				const VertexKey key2=it->first;
				if(stripper.connected(key1, key2))
				{
					result.push_back(key1);
					result.push_back(key2);
				}
				ended=true;
			}
			else
			{
				std::deque<VertexKey> leaves;
				for(typename FTree::Vertices::const_iterator it=stripper.vertices().begin();it!=stripper.vertices().end();it++)
				{
					if(it->second.adjacency.size()==1) { leaves.push_back(it->first); }
				}
				if(leaves.empty()) { ended=true; }
				else { for(std::size_t i=0;i<leaves.size();i++) { stripper.remove_vertex(leaves[i]); } }
			}
		}
		return result;
	}

	static RTree construct_rooted_ordered_tree(const FTree& ftree, const VertexKey root_key)
	{
		const typename FTree::Vertex& root_vertex=ftree.vertex(root_key);
		RTree rtree(root_key, root_vertex.value);
		std::deque< std::pair<VertexKey, VertexKey> > keys;
		for(typename FTree::Vertex::Adjacency::const_iterator it=root_vertex.adjacency.begin();it!=root_vertex.adjacency.end();it++)
		{
			keys.push_back(std::make_pair(root_key, it->first));
		}
		while(!keys.empty())
		{
			const VertexKey parent_key=keys.back().first;
			const VertexKey key=keys.back().second;
			keys.pop_back();
			const typename FTree::Vertex& vertex=ftree.vertex(key);
			for(typename FTree::Vertex::Adjacency::const_iterator it=vertex.adjacency.begin();it!=vertex.adjacency.end();it++)
			{
				const VertexKey neighbour_key=it->first;
				if(neighbour_key!=parent_key)
				{
					keys.push_back(std::make_pair(key, neighbour_key));
				}
				else
				{
					rtree.add_child(parent_key, key, it->second, vertex.value);
				}
			}
		}
		rtree.order();
		return rtree;
	}
};

}

#endif /* GRAPH_NORMALIZATION_H_ */
